package com.jxb.first;

public class MiddleOfLinkedList_876 {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode();
        listNode1.val = 1;
        ListNode listNode2 = new ListNode();
        listNode2.val = 2;
        ListNode listNode3 = new ListNode();
        listNode3.val = 3;
        ListNode listNode4 = new ListNode();
        listNode4.val = 4;
        ListNode listNode5 = new ListNode();
        listNode5.val = 5;
//        ListNode listNode6 = new ListNode();
//        listNode6.val = 6;
//        listNode5.next = listNode6;
        listNode4.next = listNode5;
        listNode3.next = listNode4;
        listNode2.next = listNode3;
        listNode1.next = listNode2;

        ListNode listNode = middleNode1(listNode1);
        System.out.println(listNode);

    }

    /**
     * 先遍历获取链表的长度，然后取出中间链表的节点，时间复杂度为O(n),空间复杂度为O(1)
     * @param head
     * @return
     */
    public static ListNode middleNode(ListNode head) {
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            length++;
            temp = temp.next;
        }

        int index = 1;
        temp = head;
        while (temp != null) {
            if (index == (length/2 + 1)) {
                return temp;
            }
            temp = temp.next;
            index++;
        }
        return null;
    }

    /**
     * 双指针(当快指针到达尾节点，慢指针就在中点了)-只需遍历一次，时间复杂度O(n)，空间复杂度为O(1)
     * @param head
     * @return
     */
    public static ListNode middleNode1(ListNode head) {
        ListNode slowP = head;
        ListNode fastP = head;
        while(fastP != null && fastP.next != null) {
            slowP = slowP.next;
            fastP = fastP.next.next;
        }
        return slowP;
    }


}
